# 作者: 郑驭泷
# 2025年03月20日12时48分46秒
# 2395042511@qq.com
class Node:
    def __init__(self, data=-1, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild  # 左节点
        self.rchild = rchild  # 右节点


class Tree:
    def __init__(self):
        self.root = None  # 树根
        self.quene = []  # 辅助队列

    def add(self, data):
        new_node = Node(data)
        self.quene.append(new_node)
        if self.root is None:
            self.root = new_node
        else:
            if self.quene[0].lchild is None:
                self.quene[0].lchild = new_node
            else:
                self.quene[0].rchild = new_node
                self.quene.pop(0)

    def pre_order(self, current_node):
        if current_node:
            print(current_node.data, end="")
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)
    def mid_order(self,current_node):
        if current_node:
            self.mid_order(current_node.lchild)
            print(current_node.data,end='')
            self.mid_order(current_node.rchild)
    def level_order(self):
        quene=[]
        quene.append(self.root)
        while quene:
            current_node=quene.pop(0)
            print(current_node.data,end="")
            if current_node.lchild:
                quene.append(current_node.lchild)
            if current_node.rchild:
                quene.append(current_node.rchild)



if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 11):
        tree.add(i)
    tree.pre_order(tree.root)
    print("\n")
    tree.mid_order(tree.root)
    print("\n")
    tree.level_order()
